package com.zwh.algorithm.foundation;

import java.util.Arrays;

/**
 * 冒泡排序:
 * 它的基本思想是对一个待排序的序列进行多次遍历，每次遍历会将相邻的两个元素进行比较，如果它们的顺序不正确就进行交换，直到所有元素都被排序为止。
 * 也就是说，每次遍历时都会让最大的元素移动到序列的末尾。
 * <p>
 * 由于每次遍历都会将一个元素移动到序列的末尾，所以需要进行n-1次遍历，其中n为序列中元素的个数。
 * 因此可以计算得出:
 * 时间复杂度: (n-1)+(n-2)+...+2+1 = n * (n-1) / 2 = n^2/2-n/2。当n很大时，则n^2占主导地位，因此时间复杂度是O(n^2)。
 * 空间复杂度: 它只需要一个额外空间(临时变量)来交换相邻的元素。由于临时变量的大小是固定的，与待排序的元素数量无关，因此空间复杂度为常数级别，即O(1)。
 *
 * @author yexi
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = new int[]{4, 1, 7, 2, 9, 3, 5, 8, 6};
        bubbleSort1(array);
        System.out.println(Arrays.toString(array));
        int[] array2 = new int[]{4, 1, 7, 2, 9, 3, 5, 8, 6};
        bubbleSort2(array2);
        System.out.println(Arrays.toString(array2));
    }

    /**
     * 将一个数组中的两个元素交换位置
     *
     * @param arr 要交换元素的数组
     * @param i   索引1，在本案例中为左边的比较数
     * @param j   索引2，在本案例中为右边的比较数
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void bubbleSort1(int[] arr) {
        // 提供一个空数组或者数组长度不足2则代表无需排序
        if (arr == null || arr.length < 2) {
            return;
        }
        // 冒泡排序致力于将找出的最大值放到最后位，而达成之后最后一位就必然是最大值
        // 那么我们就可以说，每一次冒泡后，就可以将遍历次数减掉1。
        for (int end = arr.length - 1; end > 0; end--) {
            for (int i = 0; i < end; i++) {
                // 数组临近两两比较，更大的将会往右逐步交换
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    /**
     * 实现的方法可以有很多种。
     * 这种原理跟第一种完全一样，只是换了另外一种遍历方式。
     * 这里顺带加上算法优化。
     */
    public static void bubbleSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        System.out.println("源数组: " + Arrays.toString(arr));
        // 数组中的元素个数
        int arrLength = arr.length;
        int i;
        for (i = 0; i < arrLength - 1; i++) {
            // 提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < arrLength - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    //表示有数据交换
                    flag = true;
                }
            }
            if (!flag) {
                System.out.println("提前退出冒泡循环，当前只执行到第" + (i + 1) + "次");
                //没有发生数据交换，表示当前数组已经有序，提前退出
                break;
            }
            System.out.println("当前是第" + (i + 1) + "次冒泡，冒泡后数组: " + Arrays.toString(arr));
        }
    }


}
